package com.yitiao.data_algorithms.leetcode.editor.cn;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class NextGreaterElementI{
    // 2022-08-16 09:36:56
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            Stack<Integer> stack = new Stack<>();
            // 先遍历nums2，寻找其下一个最大，用哈希表记录，遍历nums1，按key查找。
            Map<Integer, Integer> map = new HashMap<>();
            for (int i : nums2) {
                // 若当前栈有数据，且大于栈顶，则找到栈顶元素的下一个最大
                while (!stack.isEmpty()&&i>stack.peek()){
                    // 哈希表记录，同时删除栈顶元素
                    map.put(stack.pop(),i);
                }
                // 元素入栈
                stack.push(i);
            }
            int[] ans = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++)
                // 找不到的为 -1
                ans[i] = map.getOrDefault(nums1[i], -1);
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}